package Franction;

public class SimplexTable {
    Matrix aij;
    int[] bi;
    Franction[] cj;
    Franction[] cz;

    public static void main(String[] args) {
        SimplexTable t = new SimplexTable(
                new Matrix(3, 7, "1, 2, 1, 1, 0, 0, 430,3, 0, 2, 0, 1, 0, 460,1, 4, 0, 0, 0, 1, 420"),
                Franction.toList("3,6,1,0,0,0"));
        t.SolveNormal();
        t = new SimplexTable(
                new Matrix(4, 9, "-2,-3,5,1,0,0,0,4,0,1,-9,1,0,1,0,0,-3,0,4,6,3,0,0,1,0,8,0,1,1,1,0,0,0,1,0,1"),
                Franction.toList("2,-1,1,0,0,0,0"));
        t.SolveDual();
    }

    public SimplexTable(Matrix t, Franction[] cc) {
        aij = new Matrix(t.n, t.m, t.toStrIO());
        cj = new Franction[cc.length + 1];
        cz = new Franction[cc.length + 1];
        cj[0] = new Franction(67, 1);
        cz[0] = new Franction(90, 1);
        bi = new int[aij.n + 1];
        bi[0] = 'B';
        for (int i = 1; i < cj.length; i++)
            cj[i] = new Franction(cc[i - 1]);
        for (int i = 1; i < cz.length; i++)
            cz[i] = new Franction();
        Scan();
        // withM();
    }

    public void Scan() {
        for (int j = 1; j < cj.length; j++) {
            int sign1 = 0;
            int sign0 = 0;
            for (int i = 0; i < aij.n; i++) {
                if (aij.elements[i][j - 1].isEqual(1))
                    sign1 = i + 1;
                if (aij.elements[i][j - 1].isEqual(0))
                    sign0++;
            }
            if (sign1 != 0 && sign0 == aij.n - 1)
                bi[sign1] = j;
        }
        for (int j = 1; j < cj.length; j++) {
            Franction tmp = new Franction();
            for (int i = 0; i < aij.n; i++)
                tmp.Copy(tmp.add(cj[bi[i + 1]].multiply(aij.elements[i][j - 1])));
            cz[j].Copy(cj[j].minus(tmp));
        }
    }

    public boolean CheckContinueDual() {
        if (cj.length == aij.m) {
            for (int i = 0; i < aij.n; i++)
                if (aij.elements[i][aij.m - 1].isSmaller(0)) {
                    for (int j = 1; j < cj.length; j++)
                        if (aij.elements[i][j - 1].isSmaller(0))
                            return true;
                    return false;
                }
        }
        if (cj.length == aij.m - 1) {
            for (int i = 0; i < aij.n; i++) {
                if (aij.elements[i][aij.m - 1].isSmaller(0)) {
                    for (int j = 1; j < cj.length; j++) {
                        if (aij.elements[i][j - 1].isSmaller(0))
                            return true;
                    }
                    return false;
                }
            }
            for (int i = 0; i < aij.n; i++) {
                if (aij.elements[i][aij.m - 1].isEqual(0) && aij.elements[i][aij.m - 2].isSmaller(0)) {
                    for (int j = 1; j < cj.length; j++) {
                        if (aij.elements[i][j - 1].isSmaller(0))
                            return true;
                    }
                    return false;
                }
            }
        }
        return false;
    }

    public boolean CheckContinueNormal() {
        for (int j = 1; j < cj.length; j++) {
            if (cz[j].isBigger(0)) {
                for (int i = 0; i < aij.n; i++)
                    if (aij.elements[i][j - 1].isBigger(0))
                        return true;
                return false;
            }
        }
        return false;
    }

    public int[] getRotateDual() {
        int[] r = { 1, 0 };
        if (cj.length == aij.m) {
            for (int i = 0; i < aij.n; i++)
                if (aij.elements[i][aij.m - 1].isSmaller(aij.elements[r[0] - 1][aij.m - 1]))
                    r[0] = i + 1;
        }
        if (cj.length == aij.m - 1) {
            for (int i = 0; i < aij.n; i++) {
                if (aij.elements[i][aij.m - 1].isSmaller(aij.elements[r[0] - 1][aij.m - 1]))
                    r[0] = i + 1;
            }
            if (aij.elements[r[0] - 1][aij.m - 1].isEqual(0)) {
                r[0] = 1;
                for (int i = 0; i < aij.n; i++) {
                    if (aij.elements[i][aij.m - 2].isSmaller(aij.elements[r[0] - 1][aij.m - 2]))
                        r[0] = i + 1;
                }
            }
        }
        for (int j = 1; j < cj.length; j++) {
            if (aij.elements[r[0] - 1][j - 1].isSmaller(0) && cz[j].isSmaller(0)) {
                if (r[1] == 0)
                    r[1] = j;
                if ((cz[j].divide(aij.elements[r[0] - 1][j - 1]))
                        .isSmaller(cz[j].divide(aij.elements[r[0] - 1][r[1] - 1])))
                    r[1] = j;
            }
        }
        return r;
    }

    public int[] getRotateNormal() {
        int[] r = { 0, 1 };
        for (int j = 1; j < cj.length; j++)
            if (cz[j].isBigger(cz[r[1]]))
                r[1] = j;
        for (int i = 0; i < aij.n; i++) {
            if ((aij.elements[i][aij.m - 1].divide(aij.elements[i][r[1] - 1])).isBigger(0)) {
                if (r[0] == 0)
                    r[0] = i + 1;
                if ((aij.elements[i][aij.m - 1].divide(aij.elements[i][r[1] - 1]))
                        .isSmaller((aij.elements[r[0] - 1][aij.m - 1].divide(aij.elements[r[0] - 1][r[1] - 1]))))
                    r[0] = i + 1;
            }
        }
        return r;
    }

    public void Rotate(int i, int j) {
        aij.rotate(i, j);
        Scan();
    }

    public void Rotate(int[] i) {
        aij.rotate(i[0], i[1]);
        Scan();
    }

    public String toString() {
        String str = "";
        for (int j = 0; j < cj.length; j++) {
            if (j == 0)
                str += "C\t";
            else
                str += cj[j].toStrIO() + "\t";
        }
        str += "B\tM\n";
        for (int i = 0; i < aij.n; i++) {
            str += "X" + bi[i + 1] + "\t";
            for (int j = 0; j < aij.m; j++)
                str += aij.elements[i][j].toStrIO() + "\t";
            str += "\n";
        }
        for (int j = 0; j < cz.length; j++) {
            if (j == 0)
                str += "C-Z\t";
            else
                str += cz[j].toStrIO() + "\t";
        }
        str += "\n";
        return str;
    }

    public void withM() {
        System.out.println(this);
        if (cj.length == aij.m)
            return;
        else if (cj.length == aij.m - 1) {
            int r = 1;
            for (int j = 1; j < cj.length; j++) {
                if (cz[j].isBigger(cz[r]))
                    r = j;
            }
            if (cz[r].isBigger(0))
                Rotate(aij.n, r);
        } else
            System.out.println("初始有误\n");
    }

    public void SolveDual() {
        withM();
        while (CheckContinueDual()) {
            System.out.println(this);
            Rotate(getRotateDual());
        }
        System.out.println(this);
    }

    public void SolveNormal() {
        while (CheckContinueNormal()) {
            System.out.println(this);
            Rotate(getRotateNormal());
        }
        System.out.println(this);
    }
}